package com.sx.sx1.lintcode.day717;

import java.util.LinkedList;

//通LC978答案一样
public class LC978 {
    static class Solution {
        /**
         * @param s: the given expression
         * @return: the result of expression
         */
        public int calculate(String s) {
            return f(s,0).val;
        }

        public Info f(String s,int i){
            LinkedList<String> ll = new LinkedList<>();
            int cur =0;
            Info info = new Info();
            while (i<s.length() && s.charAt(i)!=')'){
                char chr = s.charAt(i);
                if(chr==' '){
                    i++;
                    continue;
                }

                if(chr>='0' && chr <='9'){
                    cur = cur*10+(chr-'0');
                    i++;
                }else if(chr !='(') { //遇到运算符了
                    addNum(ll,cur);
                    ll.addLast(String.valueOf(chr));
                    i++;
                    cur=0;
                }else{
                    info = f(s,i+1);
                    i = info.idx+1;
                    cur = info.val;
                }
            }

            addNum(ll,cur);
            info.val = getRes(ll);
            info.idx = i;
            return info;
        }

        public int getRes(LinkedList<String> ll){
            int res =0;
            boolean add = true;
            String cur;

            while (!ll.isEmpty()){
                cur = ll.pollFirst();
                if(cur.equals("+")) add = true;
                else if(cur.equals("-")) add = false;
                else{
                    int k = Integer.valueOf(cur);
                    if(add) res+= k;
                    else res-=k;
                }
            }
            return res;
        }
        public void addNum(LinkedList<String> ll,int num){
            if(!ll.isEmpty()){
                String top = ll.peekLast();
                if(top.equals("*")) {
                    ll.pollLast();
                    int cur = Integer.valueOf(ll.pollLast());
                    num = cur*num;
                }

                if(top.equals("/")){
                    ll.pollLast();
                    int cur = Integer.valueOf(ll.pollLast());
                    num= cur/num;
                }
            }
            ll.add(String.valueOf(num));
        }
        static class Info{
            public int idx;
            public int val;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.calculate("3+2*2"));
        System.out.println(obj.calculate(" 3/2 "));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
980 · 基础计算器 II
算法
中等
通过率
49%

题目
题解25
笔记
讨论53
排名
记录
描述
实现一个基础计算器来计算一个简单表达式字符串。

这个表达式字符串只包含 非负 整数，运算符 +, -, *, / 以及空格 。 整数除法应该舍去小数。

你可以假设给出的表达式总是合理的。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


请 不要 使用内置的计算表达式字符串的函数

样例
例1:

输入:
"3+2*2"
输出:
7
例2:

输入:
" 3/2 "
输出:
1
相关知识
学习《2024年6月北美大厂最新面试真题精讲》课程中的相关内容 ，了解更多相关知识！
标签
企业
Facebook
Airbnb
相关题目

849
基础计算器 III
困难

978
基础计算器
中等
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
已开启智能提示
发起考试
30 分 00 秒
123456789
public class Solution {
    /**
     * @param s: the given expression
     * @return: the result of expression

public int calculate(String s) {
    // Write your code here
}
}
控制台
        历史提交

 */